import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Leetcode {
}

//leetcode:56:合并区间
class Solution {
    public int[][] merge(int[][] intervals) {
        //以左端点进行排序
        Arrays.sort(intervals , (a, b) -> {
            return a[0] - b[0];
        });

        //记录第一区间
        int left = intervals[0][0] , right = intervals[0][1];
        List<int[]> ret = new ArrayList<>();
        //遍历剩余的区间
        for(int i = 1; i < intervals.length; i++){
            //得到区间
            int a = intervals[i][0] , b = intervals[i][1];
            //如果此时的区间在记录的区间里就代表这两个区间是可以合并的
            if(a <= right){
                //此时的右区间就是这两个区间的右区间最大值
                right = Math.max(right,b);
            }else{
                //如果不能合并就将此时的区间放入集合中
                ret.add(new int[]{left,right});
                //同更新新的记录区间
                left = a;
                right = b;
            }
        }
        //确保最后一个区间的放入
        ret.add(new int[]{left,right});
        return ret.toArray(new int[0][]);
    }
}

//leetcode:435:无重叠区间
class Solution2 {
    public int eraseOverlapIntervals(int[][] intervals) {
        //以左区间排序
        Arrays.sort(intervals,(a,b)->{
            return a[0]-b[0];
        });
        int n = intervals.length ,left = intervals[0][0], right = intervals[0][1];
        int ret = 0;
        for(int i = 1; i < n; i++){
            int a = intervals[i][0] , b = intervals[i][1];
            if(a < right){
                //如果遇到重叠的我们就要更新right为这两个区间的最小值
                right = Math.min(b,right);
                //并记录要删除的区间个数
                ret++;
            }else{
                //如果不重叠就更新新的右区间
                right = b;
            }
        }
        return ret;
    }
}

//leetcode:452:用最少数量的箭引爆气球
class Solution3 {
    public int findMinArrowShots(int[][] points) {
        //按照左端点排序，如果左端点相同就按照右端点排序
        Arrays.sort(points,(a,b)->{
            return a[0]>b[0]?1:-1;
        });
        int n = points.length,right = points[0][1];
        int ret = 1;
        for(int i = 1; i < n; i++){
            int a = points[i][0] , b = points[i][1];
            //判断是否重叠
            if(a <= right){
                //更新右端点
                right = Math.min(right,b);
            }else{
                //如果不重叠就加一
                ret++;
                right = b;
            }
        }
        return ret;
    }
}

//leetcode:397:整数替换
class Solution4 {
    public int integerReplacement(int n) {
        int ret = 0;
        while (n > 1) {
            if (n % 2 == 0) {
                ret++;
                n /= 2;
            } else {
                if(n == 3){
                    ret += 2;
                    n = 1;
                }else if (n % 4 == 1) {
                    // n/2 == (n-1)/2
                    n /= 2;
                    ret+=2;
                } else if (n % 4 == 3) {
                    // n / 2 + 1 = (n+1) / 2
                    n = n / 2 + 1;
                    ret += 2;
                }
            }
        }
        return ret;
    }
}